package 排序算法.分治排序;

import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

/**
 * 使用分治思想和forkjoin框架对字符串进行快速排序
 *
 * 重要：
 *  对于大量数据进行处理的重要思路。
 *
 */
public class QuickRecureSort {
    public static void main(String[] args) {
        String input = "tuvwxjklmnopqrsyzabcdefghi";
        char[] chars = input.toCharArray();
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        forkJoinPool.invoke(new SortTask(chars,0,chars.length));
        String sorted = String.valueOf(chars);
        System.out.println(sorted);
    }

    static class SortTask extends RecursiveAction {
        private static final int TTHRESHOLD = 10; // 阈值，小于该阈值时使用单线程排序
        private char[] arrays;
        private int start;  // 起点
        private int end; // 终止

        public SortTask(char[] arrays, int start, int end) {
            this.arrays = arrays;
            this.start = start;
            this.end = end;
        }
        @Override
        protected void compute() {
            if(end - start <= TTHRESHOLD){
                Arrays.sort(arrays,start,end);
            }else {
                //分割数组
                int mid = (start + end) / 2;
                // 创建子任务
                SortTask left = new SortTask(arrays,start,mid);
                SortTask right = new SortTask(arrays,mid,end);
                // 合并子任务,并行执行
                invokeAll(left,right);
                // 然后合并结果
                merge(arrays,start,mid,end);
            }
        }

        private void merge(char [] arrays,int start,int mid,int end){
            char [] tmp = new char[end-start];
            int i = start,j = mid,k = 0;
            //归并
            while (i < mid && j< end){
                if(arrays[i] <= arrays[j]){
                    tmp[k++] = arrays[i++];
                }else{
                    tmp[k++] = arrays[j++];
                }
            }
            while (i < mid){
                tmp[k++] = arrays[i++];
            }
            while (j < end){
                tmp[k++] = arrays[j++];
            }
            // 然后将tmp数组拷贝回原数组
            System.arraycopy(tmp,0,arrays,start,end-start);
        }
    }
}
